package com.xmmxjy.dw.util;

import com.xmmxjy.dw.entity.Tag;

import java.util.ArrayList;
import java.util.List;


public class MinHeapFloat {
    // 堆的存储结构 - 数组    
    private Tag[] data;

    /**
     * 初始化堆中的数据,以int的最小值作为初始值
     *
     * @param k
     */
    public MinHeapFloat(int k)
    {
        this.data = new Tag[k];
        for(int i=0;i<k;i++){
            data[i] = new Tag(Float.MIN_VALUE);
        }
    }

    private void adjustHeap(int i)
    {
        //获取左右结点的数组下标
        int l = left(i);
        int r = right(i);

        // 这是一个临时变量，表示 跟结点、左结点、右结点中最小的值的结点的下标
        int min = i;

        // 存在左结点，且左结点的值小于根结点的值
        if (l < data.length && data[l].compareTo(data[i]) < 0 ){
            min = l;
        }
        // 存在右结点，且右结点的值小于以上比较的较小值
        if (r < data.length && data[r].compareTo(data[min]) < 0){
            min = r;
        }

        // 左右结点的值都大于根节点，直接return，不做任何操作
        if (i == min)
            return;

        // 交换根节点和左右结点中最小的那个值，把根节点的值替换下去
        swap(i, min);

        // 由于替换后左右子树会被影响，所以要对受影响的子树再进行adjustHeap
        adjustHeap(min);
    }

    /**
     * 获取右结点的数组下标
     * @param i
     * @return
     */
    private int right(int i)
    {
        return (i + 1) << 1;
    }

    /**
     * 获取左结点的数组下标
     * @param i
     * @return
     */
    private int left(int i)
    {
        return ((i + 1) << 1) - 1;
    }

    /**
     * 交换元素位置
     *
     * @param i
     * @param j
     */
    private void swap(int i, int j)
    {
    	
    	Tag tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }

    /**
     * 将数值加入到堆中
     *
     * @param element
     */
    public void add(Tag element)
    {
        if(element.compareTo(data[0]) > 0) {
            data[0] = element;
            adjustHeap(0);
        }
    }

    public Tag[] getData(){
        return data;
    }

    @Override
    public String toString(){
        StringBuilder builder = new StringBuilder();
        builder.append("{");
        for (int i=0;i<data.length;i++){
            builder.append(data[i]);
            if(i!=data.length-1){
                builder.append(",");
            }
        }
        builder.append("}");

        return builder.toString();
    }
    
    public static void main(String[] args){

        int[] a = {12,1,5425,12,43,734,343,999,8,99,55,2,222,444,11};
        List<Tag> tagList = new ArrayList<Tag>();
        for (int i = 0; i <20; i++) {
            Tag m = new Tag(1.01f + i);
            tagList.add(m);
		}

        //求最大的10个
        int k=10;

        MinHeapFloat heap = new MinHeapFloat(k);
        for(Tag i:tagList){
            heap.add(i);
        }

        System.out.print(heap);
    }
}